"""
换零钱
给了面值为50元、20元、10元、5元、1元的五种零钱若干，思考把面值100元人民币换成零钱一共有多少种方式？
"""

coin_value = {
    1: 1,
    2: 5,
    3: 10,
    4: 20,
    5: 50,
}


def cc(mount, coin_kind=5):
    if mount == 0:
        return 1
    elif mount < 0 or coin_kind == 0:
        return 0

    return cc(mount, coin_kind - 1) + cc(mount - denomination(coin_kind), coin_kind)


def denomination(coin_kind):
    return coin_value[coin_kind]


if __name__ == "__main__":
    print(cc(100))  # 343
    print(cc(200))  # 2930
    print(cc(600))  # 143728
